翻訳と辞書 Words near each other ・ Trapezitinae ・ Trapezitsa ・ Trapezium ・ Trapezium (bone) ・ Trapezium Cluster ・ Trapezius muscle ・ Trapezo-rhombic dodecahedron ・ Trapezoaia River ・ Trapezohedron ・ Trapezoid ・ Trapezoid (band) ・ Trapezoid (disambiguation) ・ Trapezoid body ・ Trapezoid bone ・ Trapezoid E ・ Trapezoid graph ・ Trapezoid ligament ・ Trapezoid line ・ Trapezoidal distribution ・ Trapezoidal rule ・ Trapezoidal rule (differential equations) ・ Trapezoidal thread forms ・ Trapezoidal wing ・ Trapezophoron ・ Trapezopolis ・ Trapezoptera ・ Trapezus ・ Trapezus, Arcadia ・ TrapGold ・ Traphagen Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Trapezoid graph ： ウィキペディア英語版 Trapezoid graph In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, Golumbic, and Pinter in 1988. There exists $(n\backslash log\; n)$ algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique. == Definitions and characterizations == Given a channel, a pair of two horizontal lines, a trapezoid between these lines is defined by two points on the top and two points on the bottom line. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. The interval order dimension of a partially ordered set, , is the minimum number d of interval orders P1 … Pd such that P = P1∩…∩Pd. The incomparability graph of a partially ordered set is the undirected graph $G=(X,\; E)$ where ''x'' is adjacent to ''y'' in G if and only if ''x'' and ''y'' are incomparable in P. An undirected graph is a trapezoid graph if and only if it is the incomparability graph of a partial order having interval order dimension at most 2.〔Ido Dagan, Martin Charles Golumbic, and Ron Yair Pinter. Trapezoid graphs and their coloring. Discrete Appl. Math., 35–46, 1988.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Trapezoid graph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.